package interview;

import java.util.*;

public class Solution {

    /**
     * 36. 有效的数独
     * 使用3个9 * 9的二维数组，其中boolean[k][num]分别代表第k行、第k列、第k个3 * 3的宫内的num是否已经存在
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9];
        boolean[][] col = new boolean[9][9];
        boolean[][] box = new boolean[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int cur = board[i][j] - '1';
                    if (row[i][cur] || col[j][cur] || box[(i / 3) * 3 + j / 3][cur]) {
                        return false;
                    } else {
                        row[i][cur] = true;
                        col[j][cur] = true;
                        box[(i / 3) * 3 + j / 3][cur] = true;
                    }
                }
            }
        }

        return true;
    }

    /**
     * 918. 环形子数组的最大和
     * 分为两种情况 1.不跨边界，直接当作非环形求最大子数组和 2.跨边界，整个数组和减去最小的子数组和。两种情况取最大值
     *
     * @param nums
     * @return
     */
    public int maxSubarraySumCircular(int[] nums) {
        int curMax = nums[0], curMin = nums[0], maxSum = nums[0], minSum = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curMax = Math.max(curMax + nums[i], nums[i]);
            maxSum = Math.max(maxSum, curMax);

            curMin = Math.min(curMin + nums[i], nums[i]);
            minSum = Math.min(minSum, curMin);

            sum += nums[i];
        }

        return maxSum > 0 ? Math.max(maxSum, (sum - minSum)) : maxSum;
    }

    /**
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> nums1[a[0]] + nums2[a[1]]));

        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            pq.offer(new int[]{i, 0});
        }

        while (k-- > 0 && !pq.isEmpty()) {
            int[] curMin = pq.poll();
            result.add(Arrays.asList(nums1[curMin[0]], nums2[curMin[1]]));

            if (curMin[1] + 1 < nums2.length) {
                pq.offer(new int[]{curMin[0], curMin[1] + 1});
            }
        }

        return result;
    }

    /**
     * 67. 二进制求和
     * 从后向前算，设一个变量保存当前的进位数，最后将结果字符串逆序
     *
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int surplus = 0;
        while (i >= 0 || j >= 0 || surplus > 0) {
            int curA = i >= 0 ? a.charAt(i) - '0' : 0;
            int curB = j >= 0 ? b.charAt(j) - '0' : 0;

            sb.append((curA + curB + surplus) % 2);
            surplus = (curA + curB + surplus) / 2;

            i--;
            j--;
        }

        return sb.reverse().toString();
    }

    /**
     * 9. 回文数
     *
     * @param x
     * @return
     */
    public boolean isPalindrome(int x) {
        // 特殊情况处理：当x为负数时，它不是回文数。
        // 另外，如果x的最后一位是0，为了使它成为回文数，x必须是0。
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10; // 反转数字的后半部分
            x /= 10; // 去掉最后一位数字
        }

        // 当数字长度为奇数时，我们可以通过revertedNumber/10去掉中间的数字。
        // 因为中间的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }

    /**
     * 190. 颠倒二进制位
     *
     * @param n
     * @return
     */
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            // 将结果左移一位，为新的最低位腾出空间
            result <<= 1;
            // 加上n的最低位
            result |= (n & 1);
            // 将n右移一位，处理下一位
            n >>= 1;
        }
        return result;
    }

    /**
     * 191. 位1的个数
     *
     * @param n
     * @return
     */
    public int hammingWeight(int n) {
        int count = 0;

        while (n > 0) {
            if ((n & 1) == 1) {
                count++;
            }
            n >>= 1;
        }

        return count;
    }

    /**
     * 136. 只出现一次的数字
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    /**
     * 137. 只出现一次的数字 II
     * 统计每一位为1的次数然后取模3，结果不为0的位是1，其余位为0
     *
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {  // 遍历每一位
            int sum = 0;
            for (int num : nums) {
                // 统计第i位是否为1
                sum += (num >> i) & 1;
            }
            if (sum % 3 != 0) {  // 模3不为0说明该位是1
                result |= (1 << i);  // 设置结果的该位为1
            }
        }
        return result;
    }

    /**
     * 201. 数字范围按位与
     * <p>
     * 实际上是求 left 和 right 的最长公共前缀，因此只要让right不断清除为1的最低位直到 <= left
     *
     * @param left
     * @param right
     * @return
     */
    public int rangeBitwiseAnd(int left, int right) {
        while (left < right) {
            // 清除right的最低有效位1
            right = right & (right - 1);
        }
        return right;
    }

    /**
     *
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        int n = digits.length;

        // 从最低位开始遍历
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                // 如果当前位小于9，直接加一然后返回
                digits[i]++;
                return digits;
            }
            // 当前位是9，则置为0，继续循环给更高一位加一
            digits[i] = 0;
        }

        // 如果所有位都是9，则需要扩展数组，并将首位置为1
        int[] newNumber = new int[n + 1];
        newNumber[0] = 1;
        return newNumber;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] nums = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                nums[i][j] = in.nextInt();
            }
        }

        int[][] prefix = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] +
                        nums[i - 1][j - 1];
            }
        }

        int[] result = new int[n];

        for (int i = 1; i <= n; i++) {
            int count = 0;
            int required = i * i / 2;
            if (i * i % 2 != 0) {
                result[i - 1] = 0;
                continue;
            }
            for (int x = 0; x <= n - i; x++) {
                for (int y = 0; y <= n - i; y++) {
                    int xEnd = x + i;
                    int yEnd = y + i;
                    int ones = prefix[xEnd][yEnd] - prefix[x][yEnd] - prefix[xEnd][y] +
                            prefix[x][y];
                    if (ones == required) {
                        count++;
                    }
                }
            }
            result[i - 1] = count;
        }


        for (int res : result) {
            System.out.println(res);
        }
    }

}
